﻿// 0913train01.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <limits>
#include <unordered_map>
#include <unordered_set>

using namespace std;

/*
 给定M (0<M<=30)个字符(a-z)，
 从中取出任意字符(每个字符只能用一次)拼接成长度为N (0<N<=5)的字符串，
 要求相同的字符不能相邻，计算出给定的字符列表能拼接出多少种满足条件的字符串，
 输入非法或者无法拼接出满足条件的字符串则返回0

输入描述
给定的字符列表和结果字符串长度，中间使用空格(" ")拼接

输出描述
满足条件的字符串个数

输入
aabc 3
输出
8
 */
class Solution01
{
public:
    void backTrack(string& sort_str, vector<bool>&used)
    {
        //保存结果
        if (track.size()==target_len)
        {
            string res;
            for (auto&ch:track)
            {
                res += ch;
            }
            result.insert(res);
            return;
        }

        for (int i=0; i<str_size; i++)
        {
            if (used[i]) continue;
            if (i > 0 && sort_str[i] == sort_str[i - 1] && !used[i - 1]) continue;
            if (sort_str[i] == track.back()) continue;

            //做选择
            used[i] = true;
            track.push_back(sort_str[i]);
            //回溯
            backTrack(sort_str, used);
            //撤销选择
            used[i] = false;
            track.pop_back();
        }
        
    }
    Solution01 (string&origin_str, int length)
    {
        str_size = origin_str.size();
        target_len = length;

        //排序，用于剪枝
        vector<char>sort_origin;
        for (auto&ch:origin_str)
        {
            sort_origin.push_back(ch);
        }
        sort(sort_origin.begin(), sort_origin.end());
        string sort_str;
        for (auto&ch:sort_origin)
        {
            sort_str += ch;
        }

        vector<bool>used(str_size, false);
        for (int i=0; i<str_size; i++)
        {
            if (used[i]) continue;
            //做选择
            used[i] = true;
            track.push_back(sort_str[i]);
            //回溯
            backTrack(sort_str, used);
            //撤销选择
            used[i] = false;
            track.pop_back();
        }

        cout << result.size();
	    //Solution01
    }
private:
    int str_size = 0, target_len = 0;
    vector<char>track;
    unordered_set<string>result;
};

/*
 屏幕给出 1 ~ 9 中任意 4 个不重复的数字，
 可拼成的数字从小到大排列位于第 N 位置的数字，
 其中 N 为给出数字中最大的（如果不到这么多数字则给出最后一个即可）
注意：
- 2 可以当作 5 来使用，5 也可以当作 2 来使用进行数字拼接，且屏幕不能同时给出 2 和 5；
- 6 可以当作 9 来使用，9 也可以当作 6 来使用进行数字拼接，且屏幕不能同时给出 6 和 9。
如给出：1，4，8，7，则可以拼接的数字为：
1，4，7，8，14，17，18，41，47，48，71，74，78，81，84，87，147，148，178 … (省略后面的数字)
那么第 N（即8）个的数字为 41

输入描述
输入以逗号分隔的 4 个 int 类型整数的字符串

输出描述
输出为这几个数字可拼成的数字从小到大排列位于第 N （N为输入数字中最大的数字）位置的数字，
如果输入的数字不在范围内或者有重复，则输出-1

输入
1,4,8,7
输出
41
可以构成的数字按从小到大排序为：
1，4，7，8，14，17，18，41，47，48，71，74，78，81，84，87，147，148，178 … （省略后面的数字），
故第8个为41
 */
class Solution02
{
public:
    bool isAvaiable(vector<int>& num_vec, int i)
    {
        int curr = num_vec[i];
        if (linked_map.count(curr)>0)
        {
            int linked_num = linked_map.at(curr);
            if (track_set.count(linked_num) > 0)
                return false;
        }
        return true;
    }

    void backTrack(vector<int>&num_vec, vector<bool>&used)
    {
        //处理结果
        string num_str;
        for (auto& ch_item : track)
        {
            num_str += to_string(ch_item);
        }
        if (!num_str.empty())
        {
            result.push_back(stoi(num_str));
        }

        if (track.size() == v_size) return;

        for (int i=0; i<v_size; i++)
        {
            if (used[i]) continue;
            bool is_available = isAvaiable(num_vec, i);
            if (!is_available) continue;

            //做选择
            used[i] = true;
            track.push_back(num_vec[i]);
            track_set.insert(track.back());
            //回溯
            backTrack(num_vec, used);
            //撤销选择
            used[i] = false;
            track_set.erase(track.back());
            track.pop_back();
        }

        //backTrack
    }
    Solution02(vector<int>&num_vec)
    {
	    //4个不重复的数字
        //2 5不能同时出现，6 9不能同时出现
        unordered_set<int>verify_set;
        bool is_verify = true;
        //最大数字
        int target_i = -1;
        for (auto&num:num_vec)
        {
            if (linked_map.count(num)>0)
            {
                int linked_num = linked_map.at(num);
                if (verify_set.count(linked_num) > 0)
                {
                    is_verify = false;
                    break;
                }
            }
            if (verify_set.count(num)>0)
            {
                is_verify = false;
                break;
            }
            if (num==0)
            {
                is_verify = false;
                break;
            }

            verify_set.insert(num);
            target_i = max(target_i, num);
        }

        if (!is_verify)
        {
            cout << -1;
            return;
        }

        vector<int>new_vec;
        for (auto&num:num_vec)
        {
	        if (linked_map.count(num)>0)
	        {
                int linked_num = linked_map.at(num);
                new_vec.push_back(linked_num);
	        }
            new_vec.push_back(num);
        }
        num_vec = new_vec;

        v_size = num_vec.size();

        vector<bool>used(v_size, false);

        for (int i=0; i<v_size; i++)
        {
            if (used[i]) continue;
            //做选择
            used[i] = true;
            track.push_back(num_vec[i]);
            track_set.insert(track.back());
            //回溯
            backTrack(num_vec, used);
            //撤销选择
            used[i] = false;
            track_set.erase(track.back());
            track.pop_back();
        }
        sort(result.begin(), result.end());

        cout << result[target_i-1];
        //Solution02
    }
private:
    int v_size = 4;
    vector<int>track;
    vector<int>result;
    unordered_set<int>track_set;
    unordered_map<int, int>linked_map = { {2,5},{5,2},{6,9},{9,6} };
};


/*
给定一个数组，里面有 6 个整数，求这个数组能够表示的最大 24 进制的时间是多少，
输出这个时间，无法表示输出 invalid

输入描述
输入为一个整数数组，数组内有六个整数
输入整数数组长度为 6，不需要考虑其它长度，元素值为 0 或者正整数，6 个数字每个数字只能使用一次
输出描述
输出为一个 24 进制格式的时间，或者字符串“invalid”

输入
[0,2,3,0,5,6]
输出
23:56:00
 */
class Solution03
{
public:
    int getNum(int num_1, int num_2)
    {
        stringstream num_sstream;
        num_sstream << num_1 << num_2;
        string hour_str = num_sstream.str();
        int res = stoi(hour_str);
        return res;
    }

    int changeNum(vector<int>&track)
    {
        //判断是否合法
        int hour = getNum(track[0], track[1]);
        bool is_hour = hour >= 0 && hour <= 23;
        if (!is_hour) return -1;

        int minute = getNum(track[2], track[3]);
        bool is_minute = minute >= 0 && minute <= 59;
        if (!is_minute) return -1;

        int second = getNum(track[4], track[5]);
        bool is_second = second >= 0 && second <= 59;
        if (!is_second) return -1;

        //全部转成秒
        int res = 0;
        res += hour * 60 * 60;
        res += minute * 60;
        res += second;
        return res;
        //changeNum
    }
    void backTrack(vector<int>& num_vec, vector<bool>&used)
    {
        if (track.size() == v_size)
        {
            int track_val = changeNum(track);
            if (track_val!=-1)
            {
                stringstream track_sstream;
                track_sstream << track[0] << track[1] << ':';
                track_sstream << track[2] << track[3] << ':';
                track_sstream << track[4] << track[5];
                string track_str = track_sstream.str();
                result.push_back(make_pair(track_str, track_val));
            }

            return;
        }

        for (int i=0; i<v_size; i++)
        {
            if (used[i]) continue;
            //做选择
            used[i] = true;
            track.push_back(num_vec[i]);
            //回溯
            backTrack(num_vec, used);
            //撤销选择
            used[i] = false;
            track.pop_back();
        }
    }
    Solution03(vector<int>&num_vec)
    {
        vector<bool>used(v_size, false);
        for (int i=0; i<num_vec.size(); i++)
        {
            //做选择
            used[i] = true;
            track.push_back(num_vec[i]);
            //回溯
            backTrack(num_vec, used);
            //撤销选择
            used[i] = false;
            track.pop_back();
        }

        if (result.empty())
        {
            cout << "invalid";
            return;
        }

        sort(result.begin(), result.end(), [](pair<string,int>&p_1,pair<string,int>&p_2)
            {
                return p_1.second > p_2.second;
            });

        cout << result[0].first;
        //Solution03
    }
private:
    int v_size = 6;
    vector<int>track;
    vector<pair<string, int>>result;
};


/*
0：a,b,c
1：d,e,f
2：g,h,i
3：j,k,l
4：m,n,o
5：p,q,r
6：s,t
7：u,v
8：w,x
9：y,z
输入一串数字后，通过数字和字母的对应关系可以得到多个字母字符串
（要求按照数字的顺序组合字母字符串）;
屏蔽字符： 屏蔽字符中的所有字母不能同时在输出的字符串出现，如屏蔽字符是 abc，
则要求字符串中不能同时出现 a，b，c，但是允许同时出现 a，b；a，c；b，c 等
给定一个数字字符串和一个屏蔽字符串，输出所有可能的字符组合；
例如输入数字字符串 78 和屏蔽字符串 ux，输出结果为 uw，vw，vx；
数字字符串 78，可以得到如下字符串： uw，ux，vw，vx；
由于 ux 是屏蔽字符串，因此排除 ux，最终的输出时 uw，vw，vx

输入描述
第一行输入为一串数字字符串，数字字符串中的数字不允许重复，数字字符串的长度大于 0，小于等于 5；
第二行输入是屏蔽字符，屏蔽字符的长度一定小于数字字符串的长度，屏蔽字符串中字符不会重复。

输出描述
输出可能的字符串组合

输入
78
ux
输出
uw,vw,vx,
 */
class Solution04
{
public:
    bool isTrackVerify()
    {
        string track_str;
        for (auto&ch:track)
        {
            track_str += ch;
        }

        if (track_str.size() < exclu_str_.size()) return true;
        if (track_str.size() == exclu_str_.size())
        {
            if (track_str == exclu_str_) return false;
            return true;
        }
        
        string curr_sub = track_str.substr(0, exclu_str_.size());
        if (curr_sub == exclu_str_) return false;
        //abc ab
        int old_left = 0;
        for (int left=1, right= exclu_str_.size(); right<track_str.size(); left++,right++)
        {
            curr_sub.erase(old_left, 1);
            curr_sub += track_str[right];
            if (curr_sub == exclu_str_) return false;
            old_left = left;
        }
        return true;
    }

    void backTrack(vector<char>&exec_vec, int start)
    {
        if (!isTrackVerify()) return;

        if (track.size()==target_size)
        {
            string track_str;
            for (auto& ch : track)
            {
                track_str += ch;
            }
            result.push_back(track_str);
            return;
        }

        for (int i= start; i<exec_vec.size(); i++)
        {
            char curr_char = exec_vec[i];
            int curr_combine = linked_map.at(curr_char);
            if (track_set.count(curr_combine) > 0) continue;
            //选择
            track.push_back(curr_char);
            track_set.insert(curr_combine);
            //回溯
            backTrack(exec_vec, i+1);
            //撤销选择
            track.pop_back();
            track_set.erase(curr_combine);
        }

        //backTrack
    }
    Solution04(string&num_str, string&exclu_str)
    {
        //建表，几个集合拼在一起，如果track_set.count(key)>0
		for (int i=0; i<combine_vec.size(); i++)
		{
            string combine_str = combine_vec[i];
            vector<char>ch_vec;
            stringstream sstream(combine_str);
            string token;
            while (getline(sstream, token, ','))
            {
                char token_ch = token[0];
                ch_vec.push_back(token_ch);
                linked_map[token_ch] = i;
            }
            combine_map[i] = ch_vec;
		}
        exclu_str_ = exclu_str;
        target_size = num_str.size();

        vector<char>exec_vec;
        for (auto& num_ch : num_str)
        {
            vector<char>ch_vec = combine_map[num_ch - '0'];
            for (auto& ch : ch_vec)
            {
                exec_vec.push_back(ch);
            }
        }

        
        for (int i=0; i<exec_vec.size(); i++)
        {
            //做选择
            track.push_back(exec_vec[i]);
            int ch_combine = linked_map.at(exec_vec[i]);
            track_set.insert(ch_combine);
            //回溯
            backTrack(exec_vec, i+1);
            //撤销选择
            track_set.erase(ch_combine);
            track.pop_back();
        }

        for (auto&str:result)
        {
            cout << str << ',';
        }
	    //Solution04
    }
private:
    string exclu_str_;
    int target_size = 0;
    vector<char>track;
    vector<string>result;
    unordered_set<int>track_set;
    unordered_map<char, int>linked_map;
    unordered_map<int, vector<char>>combine_map;
    vector<string>combine_vec = {
    	"a,b,c","d,e,f","g,h,i","j,k,l",
		"m,n,o","p,q,r","s,t","u,v","w,x","y,z"
    };
};

int main()
{
	{
        string num_str;
        cin >> num_str;
        string exclu_str;
        cin >> exclu_str;

        Solution04 solu(num_str, exclu_str);

        return 0;
	}
	{
        string input;
        getline(cin, input);
        input = input.substr(1, input.size() - 2);
        stringstream oh_sstream(input);
        string token;
        vector<int>num_vec;
        while (getline(oh_sstream,token,','))
        {
            num_vec.push_back(stoi(token));
        }

        Solution03 solu(num_vec);

        return 0;
	}
	{
        //1,4,8,7
        //3,6,9,5
        string input;
        getline(cin, input);
        stringstream oh_sstream(input);
        string token;
        vector<int>num_vec;
        while (getline(oh_sstream, token, ','))
        {
            num_vec.push_back(stoi(token));
        }

        Solution02 solu(num_vec);

        return 0;
	}
    string origin_str;
    int length;
    cin >> origin_str >> length;
    Solution01 solu(origin_str, length);

}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
